// https://leetcode.cn/problems/count-primes/
// Created by ade on 2022/8/26.
//
#include <iostream>
#include <vector>
#include <math.h>
#include <cstring>

using namespace std;

class Solution {
public:
    int countPrimes(int n) {
        vector<int> m(n, 1);
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (m[i] == 0) continue;
            m[i] = 0;
            count++;
            long long k = (long long) i * i;
            if (k < n) {
                while (k < n) {
                    m[k] = 0;
                    k += i;
                }
            }
        }
        return count;
    }
};


int main() {
    Solution so;
    cout << so.countPrimes(709486);
    return 0;
}